|
Algorithm characterizations are attempts to formalize the word algorithm. Algorithm does not have a generally accepted formal definition. Researchers〔cf () Andreas Blass and Yuri Gurevich "Algorithms: A Quest for Absolute Definitions" Bulletin of the European Association for Theoretical Computer Science Number 81 (October 2003), pages 195–225. Reprinted in Chapter on Logic in Computer Science Current Trends in Theoretical Computer Science World Scientific, 2004, pages 283–311 Reprinted in Church's Thesis After 70 Years Ontos Verlag, 2006, 24–57}, or http://math.ucsd.edu/~sbuss/ResearchWeb/FutureOfLogic/paper.pdf (cited in a 2007 Dershowitz–Gurevich paper): Samual R. Buss, Alexander S. Kechris, Anand Pillay, and Richard A. Shore, “The Prospects for Mathematical Logic in the Twenty-first Century”.〕 are actively working on this problem. This article will present some of the "characterizations" of the notion of "algorithm" in more detail. ''This article is a supplement to the article Algorithm.'' == The problem of definition == Over the last 200 years the definition of algorithm has become more complicated and detailed as researchers have tried to pin down the term. Indeed there may be more than one type of "algorithm". But most agree that algorithm has something to do with defining generalized processes for the creation of "output" integers from other "input" integers – "input parameters" arbitrary and infinite in extent, or limited in extent but still variable—by the manipulation of distinguishable symbols (counting numbers) with finite collections of rules that a person can perform with paper and pencil. The most common number-manipulation schemes—both in formal mathematics and in routine life—are: (1) the recursive functions calculated by a person with paper and pencil, and (2) the Turing machine or its Turing equivalents—the primitive register machine or "counter machine" model, the Random Access Machine model (RAM), the Random access stored program machine model (RASP) and its functional equivalent "the computer". When we are doing "arithmetic" we are really calculating by the use of "recursive functions" in the shorthand algorithms we learned in grade-school, for example, adding and subtracting. The proofs that every "recursive function" we can ''calculate by hand'' we can ''compute by machine'' and vice versa—note the usage of the words ''calculate'' versus ''compute''—is remarkable. But this equivalence together with the ''thesis'' (hypothesis, unproven assertion) that this includes ''every'' calculation/computation indicates why so much emphasis has been placed upon the use of Turing-equivalent machines in the definition of specific algorithms, and why the definition of "algorithm" itself often refers back to "the Turing machine". This is discussed in more detail under Stephen Kleene's characterization. The following are summaries of the more famous characterizations (Kleene, Markov, Knuth) together with those that introduce novel elements—elements that further expand the definition or contribute to a more precise definition. (mathematical problem and its result can be considered as two points in a space, and the solution consists of a sequence of steps or a path linking them. Quality of the solution is a function of the path. There might be more than one attribute defined for the path, e.g. length, complexity of shape, an ease of generalizing, difficulty, and so on. ) == Chomsky hierarchy == There is more consensus on the "characterization" of the notion of "simple algorithm". All algorithms need to be specified in a formal language, and the "simplicity notion" arises from the simplicity of the language. The Chomsky (1956) hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. It is used for classifying of programming languages and abstract machines. From the ''Chomsky hierarchy'' perspective, if the algorithm can be specified on a simpler language (than unrestricted), it can be characterized by this kind of language, else it is a typical "unrestricted algorithm". Examples: a "general purpose" macro language, like M4 is unrestricted (Turing complete), but the C preprocessor macro language is not, so any algorithm expressed in ''C preprocessor'' is a "simple algorithm". See also Relationships between complexity classes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Algorithm characterizations」の詳細全文を読む スポンサード リンク
|